module S9_5 where
-- to get access to the imported modules in Hugs do
-- :set -P../Chapter7:../Chapter5:{Hugs}/lib:{Hugs}/lib/hugs:{Hugs}/lib/exts

import Dynamic
import Graph

type AspCoord   = (Int,Int,Int)
type AspEntry   = (Int,[Int])

compAsp         :: (Graph Int Int) -> Table AspEntry AspCoord -> AspCoord
                   -> AspEntry
compAsp g c (i,j,k)
    | k==0    = (weight i j g , if i==j then [i] else [i,j])
    | otherwise = let (v1,p)   = findTable c (i,j,k-1)
                      (a,p1)   = findTable c (i,k,k-1)
                      (b,_:p2) = findTable c (k,j,k-1)
                      v2 = a+b
                  in if v1<=v2 then (v1,p) else (v2,p1++p2)

bndsAsp            :: Int -> ((Int,Int,Int),(Int,Int,Int))
bndsAsp n          = ((1,1,0),(n,n,n))

asp   :: (Graph Int Int) -> [ ((Int,Int) , AspEntry) ]
asp g = [ ((i,j) , findTable t (i,j,n)) | i<-[1..n], j<-[i+1..n]]
  where n = length (nodes g)
        t = dynamic (compAsp g) (bndsAsp n) 

graphEx  ::Graph Int Int
graphEx  = mkGraph True (1,6) [(i,j,(v!!(i-1))!!(j-1)) |i<-[1..6],j<-[1..6]]

v::[[Int]]
v = [[  0,  4,  1,  6,100,100],
     [  4,  0,  1,100,  5,100],
     [  1,  1,  0,100,  8,  2],
     [  6,100,100,  0,100,  2],
     [100,  5,  8,100,  0,  5],
     [100,100,  2,  2,  5,  0]]

baaseP245 :: Graph Int Int
baaseP245 = mkGraph True (1,6) [(i,j,(v'!!(i-1))!!(j-1)) |i<-[1..6],j<-[1..6]]

v'::[[Int]]
v' =[[  0,  4,100,100,100,  2],
     [  1,  0,  3,  4,100,100],
     [  6,  3,  0,  7,100,100],
     [  6,100,100,  0,  2,100],
     [100,100,100,  5,  0,100],
     [100,100,100,  2,  3,  0]]


{- Examples of evaluations and results 
? asp graphEx
[((1, 2), (2, [1, 3, 2])), ((1, 3), (1, [1, 3])), ((1, 4), (5, [1, 3, 6, 4])), ((1, 5), (7, [1, 3, 2, 5])), ((1, 6), (3, [1, 3, 6])), ((2, 3), (1, [2, 3])), ((2, 4), (5, [2, 3, 6, 4])), ((2, 5), (5, [2, 5])), ((2, 6), (3, [2, 3, 6])), ((3, 4), (4, [3, 6, 4])), ((3, 5), (6, [3, 2, 5])), ((3, 6), (2, [3, 6])), ((4, 5), (7, [4, 6, 5])), ((4, 6), (2, [4, 6])), ((5, 6), (5, [5, 6]))]
? asp baaseP245
[((1, 2), (4, [1, 2])), ((1, 3), (7, [1, 2, 3])), ((1, 4), (4, [1, 6, 4])), ((1, 5), (5, [1, 6, 5])), ((1, 6), (2, [1, 6])), ((2, 3), (3, [2, 3])), ((2, 4), (4, [2, 4])), ((2, 5), (6, [2, 4, 5])), ((2, 6), (3, [2, 1, 6])), ((3, 4), (7, [3, 4])), ((3, 5), (9, [3, 4, 5])), ((3, 6), (6, [3, 2, 1, 6])), ((4, 5), (2, [4, 5])), ((4, 6), (8, [4, 1, 6])), ((5, 6), (13, [5, 4, 1, 6]))]

-}
